{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path In Zigzag Labelled Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #math #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数学 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathInZigZagTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树寻路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 <strong>逐行</strong> 依次按&nbsp;&ldquo;之&rdquo; 字形进行标记。</p>\n",
    "\n",
    "<p>如下图所示，在奇数行（即，第一行、第三行、第五行&hellip;&hellip;）中，按从左到右的顺序进行标记；</p>\n",
    "\n",
    "<p>而偶数行（即，第二行、第四行、第六行&hellip;&hellip;）中，按从右到左的顺序进行标记。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/06/28/tree.png\" style=\"height: 138px; width: 300px;\"></p>\n",
    "\n",
    "<p>给你树上某一个节点的标号 <code>label</code>，请你返回从根节点到该标号为 <code>label</code> 节点的路径，该路径是由途经的节点标号所组成的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>label = 14\n",
    "<strong>输出：</strong>[1,3,4,14]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>label = 26\n",
    "<strong>输出：</strong>[1,2,6,10,26]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= label &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-in-zigzag-labelled-binary-tree](https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-in-zigzag-labelled-binary-tree](https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['14', '26']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label:\n",
    "            res.append(label)\n",
    "            label >>= 1\n",
    "\n",
    "        res = res[::-1]\n",
    "        level = len(res)\n",
    "        for i in range(level):\n",
    "            if level & 1 != i & 1:\n",
    "                continue\n",
    "            l = 2 ** i\n",
    "            r = l + l - 1\n",
    "            res[i] = r - res[i] + l\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "#         ans = []\n",
    "#         while label:\n",
    "#             ans.append(label)  # 添加当前层的数值\n",
    "#             label >>= 1  # 返回上一层\n",
    "\n",
    "#         ans = ans[::-1]  # 倒序处理，从小到大返回\n",
    "#         deep = len(ans)  # 获取结果的层数\n",
    "#         for i in range(deep):\n",
    "#             if deep & 1 != i & 1:  # 层数为奇数，反转偶数层的值；层数为偶数，反转奇数层的值\n",
    "#                 continue\n",
    "#             l = 1 << i  # 获取左节点值\n",
    "#             r = 2 ** (i + 1) - 1  # 获取右节点值\n",
    "#             ans[i] = l + r - ans[i]  # 修改成对应的镜像值（即与正常树对称的值）\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 举例14=1110b，\n",
    "# 先将14右移，变为111b，然后对除第一位外所有位取反变为100b，即它的根节点4，\n",
    "# 同理100b，右移变为10b，对除第一位外所有位取反变为11b，即它的根节点3\n",
    "# 一直到1结束。\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "#         res = []\n",
    "#         while label != 1:\n",
    "#             res.append(label)\n",
    "#             label = label >> 1\n",
    "#             print(\n",
    "#                 label.bit_length(),\n",
    "#                 bin(label),\n",
    "#                 bin((1 << (label.bit_length() - 1))),\n",
    "#                 bin((1 << (label.bit_length() - 1)) - 1),\n",
    "#                 label ^ ((1 << (label.bit_length() - 1)) - 1),\n",
    "#             )\n",
    "\n",
    "#             # 3 0b111 0b100 0b11 4\n",
    "#             # 2 0b10  0b10  0b1  3\n",
    "#             # 1 0b1   0b1   0b0  1\n",
    "\n",
    "#             # 异或取反 1 xor 1 = 0 0 xor 1 = 1\n",
    "#             # ((1 << (label.bit_length() - 1)) - 1) 相当于低位的都为1\n",
    "#             label = label ^ ((1 << (label.bit_length() - 1)) - 1)\n",
    "#             # print(label)\n",
    "#         return [1] + res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        if label == 1:\n",
    "            return [1]\n",
    "        deep = 1\n",
    "        num = label // 2\n",
    "        while num > 1:\n",
    "            deep += 1\n",
    "            num //= 2\n",
    "        ans = [label]\n",
    "        for d in range(deep, 0, -1):\n",
    "            ans.append(2**d + 2**(d-1) - 1 - ans[deep-d] // 2)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label!=0:\n",
    "            res.append(label)\n",
    "            label//=2\n",
    "        res.reverse()\n",
    "        #从倒数第二个开始\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            res[i] = 2**(i+1)-1+2**i -res[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        i = 1\n",
    "        ans = []\n",
    "        while label>2**i-1:\n",
    "            i+=1\n",
    "        a =label - 2**(i-1) + 1\n",
    "        flag = (i%2==1)\n",
    "        if not flag:\n",
    "            a = 2**(i-1) - a\n",
    "        else:\n",
    "            a = a-1\n",
    "        while i>0:\n",
    "            if not flag:\n",
    "                res = 2**(i-1)+2**(i-1)-a-1\n",
    "                ans.append(res)\n",
    "            else:\n",
    "                res = 2**(i-1)+a\n",
    "                ans.append(res)\n",
    "            i-=1\n",
    "            a = a//2\n",
    "            flag = not flag\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label //= 2\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2 ** i\n",
    "            end = 2 ** (i + 1)\n",
    "            new = end - 1 - (original - start)\n",
    "            res[i] = new \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        while row:\n",
    "            ans[row - 1] = label\n",
    "            label = ((1 << row) - 1 - label + 2 ** (row - 1)) // 2\n",
    "            row -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "      level = math.ceil(math.log2(label + 1))\n",
    "      index = label - (2**(level - 1) - 1)\n",
    "      if level % 2 == 0:\n",
    "        index = 2**(level - 1) - index + 1\n",
    "\n",
    "      answer = []\n",
    "      while level >= 1:\n",
    "        if level % 2 == 0:\n",
    "          answer.append(2**level - index)\n",
    "        else:\n",
    "          answer.append(2**(level - 1) - 1 + index)\n",
    "\n",
    "        level -= 1\n",
    "        index = (index + 1) // 2\n",
    "\n",
    "      answer.reverse()\n",
    "      return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        path = collections.deque([])\n",
    "        while label != 1:\n",
    "            path.appendleft(label)\n",
    "            depth = int(math.log(label, 2))\n",
    "            label //= 2\n",
    "            label = 2 ** depth - 1 - label + 2 ** (depth - 1)\n",
    "        \n",
    "        path.appendleft(1)\n",
    "\n",
    "        return list(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label >>= 1\n",
    "            label = label ^ (1 << (label.bit_length() - 1)) - 1\n",
    "        return [1] + res[::-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        n = 0\n",
    "        for i in range(2 ** 30):\n",
    "            if 2 ** i <= label < 2 ** (i+1):\n",
    "                n = i + 1\n",
    "                break\n",
    "        path = [label]\n",
    "        while n > 1:\n",
    "            n -= 1\n",
    "            label //= 2\n",
    "            label = 2 ** n - 1 - (label - 2 ** (n-1))\n",
    "            path.append(label)\n",
    "        path.reverse()\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        for i in range(row - 1, -1, -1):\n",
    "            ans[i] = label\n",
    "            label = ((2 << i) - 1 - label + (1 << i)) >> 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        for i in range(row - 1, -1, -1):\n",
    "            ans[i] = label\n",
    "            label = ((1 << i) - 1 ^ label) >> 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        if label == 1:\n",
    "            return [1]\n",
    "        deep = 1\n",
    "        num = label // 2\n",
    "        while num > 1:\n",
    "            deep += 1\n",
    "            num //= 2\n",
    "        ans = [label]\n",
    "        for d in range(deep, 0, -1):\n",
    "            ans.append(2**d + 2**(d-1) - 1 - ans[deep-d] // 2)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        level = 0\n",
    "        while label + 1 > 1 << level:   level += 1\n",
    "\n",
    "        ans = []\n",
    "        while level:\n",
    "            ans.append(label)\n",
    "            label = ((1 << level) + (1 << (level - 1)) - label - 1) >> 1\n",
    "            level -= 1\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        c=len(bin(label))-2\n",
    "        ans=[]\n",
    "        p=label\n",
    "        if c&1==0:\n",
    "            p=(2**(c-1)+2**c-1)-label\n",
    "        else:\n",
    "            p=label\n",
    "        while p>0:\n",
    "            if c&1:\n",
    "                ans.append(p)\n",
    "            else:\n",
    "                ans.append((2**(c-1)+2**c-1)-p)\n",
    "            p>>=1\n",
    "            c-=1\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        ans = [label]\n",
    "        level = math.log2(label) // 1\n",
    "        if level % 2 == 1:\n",
    "            start = math.pow(2, level)\n",
    "            end = math.pow(2, level + 1) - 1\n",
    "            label = int(start + end - label)\n",
    "        \n",
    "        while label > 1:\n",
    "            label = label // 2\n",
    "            ans.append(label)\n",
    "        \n",
    "        ans = ans[::-1]\n",
    "        for i in range(1, len(ans) - 1, 2):\n",
    "            start = math.pow(2, i)\n",
    "            end = math.pow(2, i + 1) - 1\n",
    "            ans[i] = int(start + end - ans[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 先计算出当前 label 所在层\n",
    "        level, h = 1, 1\n",
    "        while level < label:\n",
    "            level = 2**(h+1) - 1\n",
    "            h += 1\n",
    "        # print(\"h=\", h)\n",
    "        # print(int(log2(label)))\n",
    "\n",
    "        # 根据当前 label 计算父节点\n",
    "        def reverse_level(i, h):\n",
    "            return pow(2, h) + (pow(2, h + 1) - 1 - i)\n",
    "        ans = [label]\n",
    "        h -= 1\n",
    "        while label != 1:\n",
    "            label = reverse_level(label, h) // 2\n",
    "            ans.append(label)\n",
    "            h -= 1\n",
    "        return ans[::-1]\n",
    "\n",
    "# class Solution:\n",
    "#     def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "#         def reverse_level(i, h):\n",
    "#             return pow(2, h) + (pow(2, h + 1) - 1 - i)\n",
    "\n",
    "#         h = int(log2(label))\n",
    "#         ans = [label]\n",
    "#         while label != 1:\n",
    "#             label = reverse_level(label, h) // 2\n",
    "#             ans.append(label)\n",
    "#             h -= 1\n",
    "#         ans.reverse()\n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "#作者：九律\n",
    "#链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solutions/902668/ceng-ceng-fan-zhuan-fu-fu-de-zheng-by-my-he5s/\n",
    "#来源：力扣（LeetCode）\n",
    "#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        for i in range(row - 1, -1, -1):\n",
    "            ans[i] = label\n",
    "            # 除了最高位所有位取反，并去除最后一位\n",
    "            label = ((1 << i) - 1 ^ label) >> 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # label i 在第向下取整log(i) + 1 行，记为r\n",
    "        # i 为偶数，label i在 [2^(r-1), 2^r - 1]之间，在第2^r - i个位置上，记为c\n",
    "        # i 为奇数，label i在 i - 2^(r-1) + 1 的位置上\n",
    "        # 父亲节点在向上取整log(c)上\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            # label所在的行数\n",
    "            row = math.floor(math.log(label, 2)) + 1\n",
    "            # label所在的列数\n",
    "            if row % 2 == 0:\n",
    "                col = 2 ** row - label\n",
    "                # parent_col = max(math.ceil(math.log(col, 2)), 1)\n",
    "                # 需要保证col的值始终大于等于1\n",
    "                parent_col = max(math.ceil(col / 2), 1)\n",
    "                # 父节点所在的行数\n",
    "                parent_row = row - 1\n",
    "                # 父节点所在行起始节点的值\n",
    "                start = 2 ** (parent_row - 1)\n",
    "                # 父节点的值\n",
    "                parent = start + (parent_col - 1)\n",
    "                label = parent\n",
    "            else:\n",
    "                col = label - 2 ** (row - 1) + 1\n",
    "                # parent_col = max(math.ceil(math.log(col, 2)), 1)\n",
    "                parent_col = max(math.ceil(col / 2), 1)\n",
    "                parent_row = row - 1\n",
    "                start = 2 ** (parent_row) - 1\n",
    "                parent = start - parent_col + 1\n",
    "                label = parent\n",
    "        res.append(1)\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "\n",
    "        # 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node//2\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label//=2\n",
    "\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "\n",
    "        # 从倒数第二个开始，每隔一个，找出取反相对应的值\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2**i\n",
    "            end = 2**(i+1)\n",
    "            new = end - 1 - (original - start)\n",
    "            res[i] = new\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 1 log(1) + 1\n",
    "        # 2 log(2) + 1 log(3) + 1\n",
    "        # 3 log(4) + 1 ... log(7) + 1\n",
    "        # label i 在第向下取整log(i) + 1 行，记为r\n",
    "        # i 为偶数，label i在 [2^(r-1), 2^r - 1]之间，在第2^r - i个位置上，记为c\n",
    "        # i 为奇数，label i在 i - 2^(r-1) + 1 的位置上\n",
    "        # 父亲节点在向上取整log(c)上\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            # label所在的行数\n",
    "            row = math.floor(math.log(label, 2)) + 1\n",
    "            # label所在的列数\n",
    "            if row % 2 == 0:\n",
    "                col = 2 ** row - label\n",
    "                # parent_col = max(math.ceil(math.log(col, 2)), 1)\n",
    "                # 需要保证col的值始终大于等于1\n",
    "                parent_col = max(math.ceil(col / 2), 1)\n",
    "                # 父节点所在的行数\n",
    "                parent_row = row - 1\n",
    "                # 父节点所在行起始节点的值\n",
    "                start = 2 ** (parent_row - 1)\n",
    "                # 父节点的值\n",
    "                parent = start + (parent_col - 1)\n",
    "                label = parent\n",
    "            else:\n",
    "                col = label - 2 ** (row - 1) + 1\n",
    "                # parent_col = max(math.ceil(math.log(col, 2)), 1)\n",
    "                parent_col = max(math.ceil(col / 2), 1)\n",
    "                parent_row = row - 1\n",
    "                start = 2 ** (parent_row) - 1\n",
    "                parent = start - parent_col + 1\n",
    "                label = parent\n",
    "        res.append(1)\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = int(log2(label))+1\n",
    "        ans = [0] * row\n",
    "        while row:\n",
    "            ans[row - 1] = label\n",
    "            label = (2**row-1-label+2**(row-1))//2\n",
    "            row -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        result = []\n",
    "        #sum_line每一行的最大最小数的和。若根是第一行，则第n行的和为2 ** (n-1) + 2 ** n -1= 3 * 2 ** (n-1) - 1\n",
    "        sum_line = 3 * 2 ** (label.bit_length() - 1) - 1\n",
    "        #这一行是否需要倒置，因为从叶结点开始，开始是不需要倒置\n",
    "        is_changed = False\n",
    "        #只要label不为0，就继续循环：\n",
    "        while label:\n",
    "            if is_changed:\n",
    "                #若需要改，则将和-当前值\n",
    "                result.append(sum_line - label)\n",
    "            else:\n",
    "                result.append(label)\n",
    "            label //= 2\n",
    "            is_changed = not is_changed\n",
    "            #每行的最大最小数的和，这里其实就是下一行是上一行的2倍+1，从叶到根遍历的话，就是整除2.这里有个技巧处理根，根所在行只有1，最大与最小和为2，也符合要求\n",
    "            sum_line //= 2\n",
    "        return result[::-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        floor = 0\n",
    "        for i in range(1, 25):\n",
    "            if 2 ** i - 1 >= label:\n",
    "                floor = i\n",
    "                break\n",
    "        # 第i行的最小值是 2^(i - 1) 最大值是2 ^ i - 1\n",
    "        res = []\n",
    "        t, i = label, floor\n",
    "        while i > 0:\n",
    "            l, r = 2 ** (i - 1), 2 ** i - 1\n",
    "            rev = l + r - t\n",
    "            res.append(t)\n",
    "            t = rev >> 1\n",
    "            # print(f'i = {i}, l = {l}, r = {r}, t = {t}, rev = {rev}')\n",
    "            i -= 1\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 举例14=1110b，\n",
    "# 先将14右移，变为111b，然后对除第一位外所有位取反变为100b，即它的根节点4，\n",
    "# 同理100b，右移变为10b，对除第一位外所有位取反变为11b，即它的根节点3\n",
    "# 一直到1结束。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label = label >> 1\n",
    "            # print((1 << (label.bit_length() - 1)), label.bit_length() - 1)\n",
    "            print(\n",
    "                label.bit_length(),\n",
    "                bin(label),\n",
    "                bin((1 << (label.bit_length() - 1))),\n",
    "                label ^ (1 << (label.bit_length() - 1)),\n",
    "            )\n",
    "            label = label ^ ((1 << (label.bit_length() - 1)) - 1)\n",
    "            print(label)\n",
    "        return [1] + res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label > 0:\n",
    "            res.append(label)\n",
    "            label //= 2\n",
    "            # ↓这行别忘记\n",
    "            if label == 0:\n",
    "                break\n",
    "            depth = self.getDepth(label)\n",
    "            p = 2**depth\n",
    "            range = [p, 2*p-1]\n",
    "            #修正\n",
    "            label = sum(range) - label\n",
    "        res.reverse()\n",
    "        return res\n",
    "    def getDepth(self, label):\n",
    "        return int(math.log(label)/math.log(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        ss = [label]\n",
    "        aa = bin(label)[2:]\n",
    "        dd =len(aa)\n",
    "        while label != 1:\n",
    "            dd = dd - 1\n",
    "            label = 2**(dd - 1) + 2**dd - 1 -(label//2)\n",
    "            ss.append(label)\n",
    "        return ss[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 举例14=1110b，\n",
    "# 先将14右移，变为111b，然后对除第一位外所有位取反变为100b，即它的根节点4，\n",
    "# 同理100b，右移变为10b，对除第一位外所有位取反变为11b，即它的根节点3\n",
    "# 一直到1结束。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label >>= 1\n",
    "\n",
    "            label = label ^ ((1 << (label.bit_length() - 1)) - 1)\n",
    "        return [1] + res[::-1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "#         res = []\n",
    "#         while label != 1:\n",
    "#             res.append(label)\n",
    "#             label = label >> 1\n",
    "#             print(\n",
    "#                 label.bit_length(),\n",
    "#                 bin(label),\n",
    "#                 bin((1 << (label.bit_length() - 1))),\n",
    "#                 bin((1 << (label.bit_length() - 1)) - 1),\n",
    "#                 label ^ ((1 << (label.bit_length() - 1)) - 1),\n",
    "#             )\n",
    "\n",
    "#             # 3 0b111 0b100 0b11 4\n",
    "#             # 2 0b10  0b10  0b1  3\n",
    "#             # 1 0b1   0b1   0b0  1\n",
    "\n",
    "#             # 异或取反 1 xor 1 = 0 0 xor 1 = 1\n",
    "#             # ((1 << (label.bit_length() - 1)) - 1) 相当于低位的都为1\n",
    "#             label = label ^ ((1 << (label.bit_length() - 1)) - 1)\n",
    "#             # print(label)\n",
    "#         return [1] + res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, x: int) -> List[int]:\n",
    "        ans = [x]\n",
    "        while x != 1:\n",
    "            n = x.bit_length()  # 确定在第几层\n",
    "            fa = x // 2  # 理论上父节点\n",
    "            fa = 2**(n - 2) + (2**(n - 1) - 1 - fa)   # 计算上层fa偏移量\n",
    "            ans.append(fa)\n",
    "            x = fa\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    # 规律\n",
    "    # https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solution/chi-xiao-dou-python-jian-ji-de-dai-ma-he-q2kp/\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node // 2\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label //= 2\n",
    "\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "\n",
    "        # 从倒数第二个开始，每隔一个，找出取反相对应的值\n",
    "        for i in range(len(res) - 2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2 ** i\n",
    "            end = 2 ** (i + 1) - 1\n",
    "            new = end - (original - start)\n",
    "            res[i] = new\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        n = 1\n",
    "        while 2 ** n - 1 < label:\n",
    "            n += 1\n",
    "        ans = []\n",
    "        while n > 0:\n",
    "            ans.append(label)\n",
    "            if n % 2:\n",
    "                loc = label - 2 ** (n - 1)\n",
    "                father = loc // 2\n",
    "                label = 2 ** (n - 1) - 1 - father\n",
    "            else:\n",
    "                loc = 2 ** n - label - 1\n",
    "                father = loc // 2\n",
    "                label = 2 ** (n - 2) + father\n",
    "            n -= 1\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        a, l = math.floor(math.log2(label)), []\n",
    "        if a%2: label = 2**a+(2**(a+1)-label-1)\n",
    "        while label>1: \n",
    "            l.append(label)\n",
    "            label //=2\n",
    "        l = [1] + l[::-1]\n",
    "        for i in range(1, len(l), 2):\n",
    "            a = math.floor(math.log2(l[i]))\n",
    "            l[i] = 2**a+(2**(a+1)-l[i]-1)\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label >>= 1\n",
    "            label = label ^ (1 << (label.bit_length() - 1)) - 1\n",
    "        return [1] + res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        level = 0\n",
    "        while label + 1 > 1 << level:   level += 1\n",
    "\n",
    "        ans = []\n",
    "        while level:\n",
    "            ans.append(label)\n",
    "            label = ((1 << level) + (1 << (level - 1)) - label - 1) >> 1\n",
    "            level -= 1\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "\n",
    "        # 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node//2\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label//=2\n",
    "\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "\n",
    "        # 从倒数第二个开始，每隔一个，找出取反相对应的值\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2**i\n",
    "            end = 2**(i+1)\n",
    "            new = end - 1 - (original - start)\n",
    "            res[i] = new\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        while row:\n",
    "            ans[row - 1] = label\n",
    "            label = ((1 << row) - 1 - label + (1 << (row - 1))) // 2\n",
    "            row -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "\n",
    "        # 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node//2\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label//=2\n",
    "\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "\n",
    "        # 从倒数第二个开始，每隔一个，找出取反相对应的值\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2**i\n",
    "            end = 2**(i+1)\n",
    "            new = end - 1 - (original - start)\n",
    "            res[i] = new\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 定义两个操作，都对除了最高位1以外的位起作用\n",
    "        # 1、反转所有位，向左位移，加上目标位\n",
    "        # 2、向左位移，加上目标位，反转所有位\n",
    "        # 当二进制长度为偶数时，先执行1，否则先执行2\n",
    "        def rev_shift(n, target):\n",
    "            \"\"\"\n",
    "            先反转，再位移\n",
    "            \"\"\"\n",
    "            n ^= (1 << n.bit_length() - 1) - 1  # 反转除了第一位以外的所有位\n",
    "            n <<= 1\n",
    "            n += target\n",
    "            return n\n",
    "        \n",
    "        def shift_rev(n, target):\n",
    "            \"\"\"\n",
    "            先位移，再反转\n",
    "            \"\"\"\n",
    "            n <<= 1\n",
    "            n += target\n",
    "            n ^= (1 << n.bit_length() - 1) - 1\n",
    "            return n\n",
    "        \n",
    "        s = f'{label:b}'\n",
    "        ans = [1]\n",
    "        odd = len(s) & 1\n",
    "\n",
    "        for c in s[1:]:\n",
    "            if odd:\n",
    "                ans.append(shift_rev(ans[-1], int(c)))\n",
    "            else:\n",
    "                ans.append(rev_shift(ans[-1], int(c)))\n",
    "            odd = not odd\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    # 规律\n",
    "    # https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solution/chi-xiao-dou-python-jian-ji-de-dai-ma-he-q2kp/\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node // 2\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label //= 2\n",
    "\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "\n",
    "        # 从倒数第二个开始，每隔一个，找出取反相对应的值\n",
    "        for i in range(len(res) - 2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2 ** i\n",
    "            end = 2 ** (i + 1) - 1\n",
    "            res[i] = end - (original - start)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        # 先计算出当前 label 所在层\n",
    "        level, h = 1, 1\n",
    "        while level < label:\n",
    "            level = 2**(h+1) - 1\n",
    "            h += 1\n",
    "        # print(\"h=\", h)\n",
    "        # print(int(log2(label)))\n",
    "\n",
    "        # 根据当前 label 计算父节点\n",
    "        def reverse_level(i, h):\n",
    "            return pow(2, h) + (pow(2, h + 1) - 1 - i)\n",
    "        ans = [label]\n",
    "        h -= 1\n",
    "        while label != 1:\n",
    "            label = reverse_level(label, h) // 2\n",
    "            ans.append(label)\n",
    "            h -= 1\n",
    "        return ans[::-1]\n",
    "\n",
    "# class Solution:\n",
    "#     def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "#         def reverse_level(i, h):\n",
    "#             return pow(2, h) + (pow(2, h + 1) - 1 - i)\n",
    "\n",
    "#         h = int(log2(label))\n",
    "#         ans = [label]\n",
    "#         while label != 1:\n",
    "#             label = reverse_level(label, h) // 2\n",
    "#             ans.append(label)\n",
    "#             h -= 1\n",
    "#         ans.reverse()\n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "#作者：九律\n",
    "#链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solutions/902668/ceng-ceng-fan-zhuan-fu-fu-de-zheng-by-my-he5s/\n",
    "#来源：力扣（LeetCode）\n",
    "#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = label.bit_length()\n",
    "        ans = [0] * row\n",
    "        while row:\n",
    "            row -= 1\n",
    "            ans[row] = label\n",
    "            label = ((1 << row + 1) - 1 - label + (1 << row)) >> 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label >>= 1\n",
    "            # 这里我采用异或实现\n",
    "            label = label ^(1 << (label.bit_length() - 1)) - 1\n",
    "        return [1]+res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        ans = []\n",
    "        deep = int(log2(label)) + 1\n",
    "        while deep > 0:\n",
    "            ans.append(label)\n",
    "            if deep % 2:\n",
    "                deep -= 1\n",
    "                label //= 2\n",
    "                # 反转\n",
    "                label = 2 ** deep - 1 - label + 2 ** (deep - 1)\n",
    "            else:\n",
    "                # 反转\n",
    "                label = 2 ** deep - 1 - label + 2 ** (deep - 1)\n",
    "                label //= 2\n",
    "                deep -= 1\n",
    "\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = []\n",
    "        while label != 1:\n",
    "            res.append(label)\n",
    "            label //= 2\n",
    "        res.append(1)\n",
    "        res.reverse()\n",
    "        for i in range(len(res)-2, -1, -2):\n",
    "            original = res[i]\n",
    "            start = 2 ** i\n",
    "            end = 2 ** (i+1)\n",
    "            new = end - 1 - (original - start)\n",
    "            res[i] = new\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        res = [label]\n",
    "        row = 0\n",
    "        while (pow(2, row) - 1) < label:\n",
    "            row += 1\n",
    "        if row % 2:\n",
    "            idx = label - pow(2, row - 1) + 1\n",
    "        else:\n",
    "            idx = pow(2, row) - label\n",
    "        while row > 1:\n",
    "            row -= 1\n",
    "            idx = (idx + 1) // 2\n",
    "            if row % 2:\n",
    "                res.append(pow(2, row - 1) + idx - 1)\n",
    "            else:\n",
    "                res.append(pow(2, row) - idx)\n",
    "        return res[::-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "\n",
    "        # 行数\n",
    "        row = int(math.log2(label)) + 1\n",
    "        ans = [0]*row\n",
    "\n",
    "        while row:\n",
    "            ans[row-1] = label\n",
    "            # label的对称节点除以二就是label的父节点\n",
    "            label = ((2**(row-1) + 2**row-1) - label) // 2\n",
    "            row -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        def to_zig(num: int) -> int:\n",
    "            lv = num.bit_length()\n",
    "            if lv & 1:\n",
    "                return num\n",
    "            return (1 << lv) - 1 - (num - (1 << (lv - 1)))\n",
    "\n",
    "        def from_zig(num: int) -> int:\n",
    "            lv = num.bit_length()\n",
    "            if lv & 1:\n",
    "                return num\n",
    "            return (1 << (lv - 1)) + ((1 << lv) - 1 - num)\n",
    "\n",
    "        ans = []\n",
    "        label = from_zig(label)\n",
    "        while label > 0:\n",
    "            ans.append(to_zig(label))\n",
    "            label >>= 1\n",
    "        ans.reverse()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        a = []\n",
    "        i = 1\n",
    "        while 2 ** i - 1 < label:\n",
    "            a.append(2 ** i - 1)\n",
    "            i += 1\n",
    "        a.append(2 ** i - 1)\n",
    "        print(f'{a=}')\n",
    "        n = len(a)\n",
    "        if n % 2 == 0:\n",
    "            label = (a[-2] + 1) + (a[-1] - label)\n",
    "        ans = []\n",
    "        while label >= 1:\n",
    "            ans.append(label)\n",
    "            label //= 2\n",
    "        print(f'{ans =}')\n",
    "        if n % 2 == 1:\n",
    "            n -= 1\n",
    "        ans = ans[::-1]\n",
    "        for j in range(n, 0, -2):\n",
    "            ans[j-1] = (a[j-2] + 1) + (a[j-1] - ans[j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        row = 1\n",
    "        startrow = 1\n",
    "        while startrow*2 <= label:\n",
    "            row += 1\n",
    "            startrow *= 2\n",
    "        path = []\n",
    "        if row%2 == 0: \n",
    "            label = (1<<(row-1)) + (1<<row) -1 -label\n",
    "        print(row, label)\n",
    "        while row:\n",
    "            print(row, label, path)\n",
    "            if row%2 == 0: \n",
    "                path.append((1<<(row-1)) + (1<<row) -1 -label)\n",
    "            else:\n",
    "                path.append(label)\n",
    "            label = label>>1\n",
    "            row -= 1\n",
    "        return list(reversed(path))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        if label == 1:\n",
    "            return [1]\n",
    "        depth = 0\n",
    "        num = 0\n",
    "        while num < label:\n",
    "            num += 2**depth\n",
    "            depth += 1\n",
    "\n",
    "        path = []\n",
    "        pos = -1\n",
    "        while depth:\n",
    "            large = 2**depth - 1\n",
    "            small = 2**(depth - 1)\n",
    "           \n",
    "            if depth % 2:\n",
    "                if pos == -1:\n",
    "                    pos = label - small\n",
    "                else:\n",
    "                    pos = pos // 2\n",
    "                path.append(small + pos)\n",
    "            else:\n",
    "                if pos == -1:\n",
    "                    pos = large - label\n",
    "                else:\n",
    "                    pos = pos // 2\n",
    "                path.append(large - pos)\n",
    "            depth -= 1\n",
    "        return path[::-1]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        ss = [label]\n",
    "        aa = bin(label)[2:]\n",
    "        dd =len(aa)\n",
    "        while label != 1:\n",
    "            dd = dd - 1\n",
    "            label = 2**(dd - 1) + 2**dd - 1 -(label//2)\n",
    "            ss = [label] + ss\n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathInZigZagTree(self, label: int) -> List[int]:\n",
    "        if label==1:\n",
    "            return [1]\n",
    "        level = 1\n",
    "        nodes = 1\n",
    "        while nodes<=label:\n",
    "            level+=1\n",
    "            nodes = 2**level\n",
    "        # level-=1\n",
    "        res = [label]\n",
    "        def exchaneg(node,curr):\n",
    "            return 2**(curr-1)-node+2**(curr)-1\n",
    "        \n",
    "        if not level&1:\n",
    "            label = 2**(level-1)-label+2**(level)-1\n",
    "        label = (label)>>1\n",
    "        level -=1\n",
    "        while level>1:\n",
    "            if level&1:\n",
    "                res.append(label)\n",
    "            else:\n",
    "                res.append(exchaneg(label,level))\n",
    "            label = (label)>>1\n",
    "            level-=1\n",
    "\n",
    "        res.append(1)\n",
    "        l = 0\n",
    "        r = len(res)-1\n",
    "        while l<r:\n",
    "            tmp = res[l]\n",
    "            res[l] = res[r]\n",
    "            res[r] = tmp\n",
    "            l+=1\n",
    "            r-=1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
